package _06_deque.my_implements;

import _06_deque.Deque;

/**
 * @author: mornd
 * @dateTime: 2023/6/7 - 17:26
 * 基于单向链表实现双端队列
 */
public class LinkedListDeque<E> implements Deque<E> {
    Node<E> head;
    Node<E> tail;

    int size;
    int capacity;

    public LinkedListDeque(int capacity) {
        head = new Node<>(null);
        // 一开始头指向尾，待插入一个元素e，e就是尾，head.next = e
        tail = head;
        this.capacity = capacity;
    }

    /*
        h 1 2
            t

     */
    @Override
    public boolean offerFirst(E e) {
        if (isFull()) {
            return false;
        }
        if (isEmpty()) {
            tail = new Node<>(e);
            head.next = tail;
        } else {
            head.next = new Node<>(e, head.next);
        }
        size++;
        return true;
    }

    @Override
    public boolean offerLast(E e) {
        if (isFull()) {
            return false;
        }
        Node<E> n = new Node<E>(e);
        tail = tail.next = n;
        size++;
        return true;
    }

    @Override
    public E popFirst() {
        if (isEmpty()) {
            return null;
        }
        Node<E> first = head.next;
        head.next = first.next;
        if (first == tail) {
            tail = head;
        }
        size--;
        return first.item;
    }

    /**
     * 使用单向链表弹出尾部元素时，可以借助 size 实现，如果队列过大，效率比较低 O(n)，或者使用双向链表实现
     * @return
     */
    @Override
    public E popLast() {
        if (isEmpty()) {
            return null;
        }
        /*
            h  1,2
                 t
         */
        E r = tail.item;
        tail.item = null; // help GC ?!
        Node<E> newTail = head;
        for (int i = size; i > 1; i--) {
            newTail = newTail.next;
        }
        tail = newTail;
        size--;
        return r;
    }

    @Override
    public E peekFirst() {
        if(isEmpty()) {
            return null;
        }
        return head.next.item;
    }

    @Override
    public E peekLast() {
        if(isEmpty()) {
            return null;
        }
        return tail.item;
    }

    @Override
    public boolean isEmpty() {
        return head == tail;
    }

    @Override
    public boolean isFull() {
        return size == capacity;
    }

    static class Node<E> {
        E item;
        Node<E> next;

        Node(E item) {
            this.item = item;
        }

        Node(E item, Node<E> next) {
            this.item = item;
            this.next = next;
        }
    }
}
